package com.han.algo_ds.algorithm._24_str_pattern._02kmp;

/**
* @author hanpeng
* @version 创建时间：2020年7月26日 下午6:06:03
* @ClassName 类名称
* @Description 类描述
*/
public class KMP {
	public static void main(String[] args) {
		KMP kmp = new KMP();
		System.out.println(kmp.pattern("world", "l"));
		
	}
	public int pattern(String text,String pattern) {
		if(text==null||pattern==null) {return -1;}
		char[] textChars = text.toCharArray();
		
		int tLen = textChars.length;
		if(tLen==0) {return -1;}
		int[] next = next(pattern);
		char[] patternChars = pattern.toCharArray();
		int pLen = patternChars.length;
		if(pLen==0) {return -1;}
		if (tLen<pLen) {
			return -1;
		}
		
		
		int ti=0;
		int pi=0;
		final int deltaLen=tLen-pLen;
		
		while (pi<pLen&&ti-pi<=deltaLen) { 
			if(pi<0||textChars[ti]==patternChars[pi]) {
				ti++;
				pi++;
			} else {
				//ti 回溯  
				//
				ti=ti-(pi-1);
				pi=next[pi];
			}
		}
		
		return (pi==pLen)?(ti-pi):-1;
	}
	private static int[] next(String pattern) {
		char[] cs = pattern.toCharArray();
		int[] next=new int[cs.length];
		
		next[0]=-1;
		int i=0;
		int n=-1;
		int iMax=cs.length-1;
		while (i<iMax) {
			if(n<0||cs[i]==cs[n]) {
				next[++i]=++n;
			} else {
				n=next[n];
			}
		}
		//System.out.println(next);
		return next;
	}
	private static int[] next2(String pattern) {
		char[] cs = pattern.toCharArray();
		int[] next=new int[cs.length];
		
		
		next[0]=-1;
		int i=0;
		int n=-1;
		int iMax=cs.length-1;
		while (i<iMax) {
			if(n<0||cs[i]==cs[n]) {
				++i;
				++n;
				if(cs[i]==cs[n]) {
					next[i]=next[n];
				}
			} else {
				n=next[n];
			}
		}
		return next;
	}
}

















